1. Field of the Invention
The present invention relates to a cyclic redundancy check (CRC) circuit and a communication system having the same, and more particularly, to a cyclic redundancy check (CRC) circuit and a communication system having the same in a multi-channel serial communication system such as a high definition multimedia interface (HDMI).
2. Description of the Related Art
HDMI is a cable and interface for transmitting uncompressed digital audio and video data between an audio/video source such as a set-top box (e.g., a cable box, of a satellite receiver) or a DVD player and a display such as a digital TV. HDMI supports standard high definition video and multi-channel audio and all ATSC (advanced television systems committee) HDTV standards and 8 channel digital audio, through a single cable and only one connector at each end (a mini-plug with 19-poles). HDMI transfers audio data frequencies up to 192 kHz with a word width up to 24 bit on up to 8 channels. The band width for video data is at up to 165 MHz. Therefore it is possible to transmit all picture and sound formats of the home cinema world—including HDTV (up to the highest resolution of 1080 p)—without any loss of quality.
The Cyclic Redundancy Check is a way to detecting small changes in blocks of transmitted data and was originally developed for detection of line transmission errors. CRC (cyclic redundancy check) is an error detection method to certify reliability of transmitted/received data in serial data transmission systems and the principles of its operation are as follows. First, when a word of n-bit data is shifted by k bits and the k-shifted n-bit data is divided by a predetermined (preset) k-bit key (polynomial) value, an r-bit remainder is left. At a transmission end (of the serial data transmission system), the r-bit remainder is appended to the original n-bits, to produce (n+r) bits of data that is transmitted. At a receiving end (of the serial data transmission system), the (n+r) bits of received data is divided by the key value and, if the remainder is 0, it is determined that the received data has no error.
The CRC algorithm operates on a block or frame of data as a unit (e.g., a single large numerical value). The CRC algorithm divides this large value by a predetermined number (the CRC polynomial or generator polynomial P), leaving the remainder, which is the r-bit CRC result. The CRC result can be sent or stored along with the original data. When the data is received (or recovered from storage) the CRC algorithm can be reapplied, and the latest result compared to the original result. If an error has occurred, there will probably be a different CRC result. Most uses of CRC do not attempt to classify or locate the error (or errors), but simply arrange to repeat the data operation until no errors are detected.
The quality of generated r-bit CRC as the reminder after division is mainly influenced by the chosen generator polynomial. The selection of generator polynomial is the most important part of implementing the CRC algorithm. The polynomial is chosen to maximize the error detecting capabilities. When creating a new polynomial, general advice is to use an irreducible polynomial (over modular arithmetics), which means that the polynomial cannot be divided by any polynomial (except itself) with zero remainder. The specific CRC is defined by the polynomial P used. A degree-k polynomial, has the form 1+x+x^k. This is naturally expressed as an k+1 bit string, but the highest (x^k) term is normally implicit, leaving a k-bit string.
The CRC polynomial expression P(x) defined by the HDMI standard has an order (k) of eight, and is shown below in Equation 1.P(x)=1+x6++x7+x8  [Equation 1]
The process of generating the r CRC bits according to the HDMI CRC polynomial expression of Equation 1 is described below.
FIG. 2 is a block diagram of a conventional CRC circuit configured to implement the CRC polynomial expression of Equation 1. The CRC circuit of FIG. 2 is configured for processing serial data transmitted and received through a general mono-channel serial communication system. The symbol ⊕ represents an XOR gate or modulo-2 adder. The CRC circuit includes a plurality (r, up to or equal to, but not more than, the order k of the polynomial) of modulo-2 adders 41 and a plurality (k, e.g., k=8 for HDMI) of flip-flops 42 for delaying the input data. The r bits of the CRC output by the circuit of FIG. 2 correspond to r taps P[0], P[5], and P[6].
CRCs are based on division of polynomials over integers modulo-2. In this modular arithmetic, coefficients of polynomials are represented by only one bit. Any string of bits can be interpreted as a sequence of polynomial coefficients. The CRC algorithm treats all bit streams as binary polynomials. Any string of bits (data) can be interpreted as the coefficients of a polynomial of this sort, and to find the CRC, we divide the data by another fixed polynomial P. This pre-defined polynomial is called the devisor or CRC Polynomial. The coefficients of the remainder polynomial are the CRC. The CRC is defined as a sequence of coefficients appearing in the remainder polynomial.
Modulo-2 arithmetic allows an efficient implementation of a form of division that is fast, easy to implement, and sufficient for the purposes of error detection. Addition and subtraction operations are equivalent in modulo-2 arithmetic and both are the same as the XOR (Exclusive OR) function for bits, so it's very simple to implement in hardware. There are no carries between the bits and computing of all basic operations is less computational expensive than in normal arithmetic. That is the reason why the modular arithmetic is used.
A summary of the CRC creation process is as follows:                1. Get the n-bit data.        2. Left shift the n-bit data (by k bits) and the divide it by P.        3. The r-bit reminder of the last action is the CRC.        4. Append the first r-bit CRC to the data and transmit them together as a data frame.And a summary of the CRC check process is as follows:        1. Receive the data frame.        2. Divide it (e.g., the n bits of data) by P.        3. Compare the second r-bit CRC with the transmitted first r-bit CRC.        
The conventional hardware CRC implementation (circuit) is shown in FIG. 2. Thus, the shift register of FIG. 2 (comprised of k flip flops 42) contains k bits, equal to the length (order) of the Polynomial (Equation 1). In the conventional CRC circuit, there are up to k (but no more than k) XOR gates. The presence or absence of an XOR gate corresponds to the presence or absence of a term in the divisor polynomial P.
A CRC circuit that is identical to the CRC circuit at the transmission end is provided at the receiving end. The CRC circuit at the receiving end generates r CRC bits from the n-bits of transmitted/received data and determines the existence of an error by comparing the r generated CRC bits and the r received (e.g., transmitted) CRC bits.
In a mono-channel serial communication system, such as a universal serial bus (USB), CRC bits are instantly generated when the transmission of serial data is completed real time. However, in a multi-channel serial communication system such as HDMI, since multiple data are transmitted simultaneously in parallel through multiple channels, there is a need to generate CRC bits suitable for the multi-channel transmission.